绝密★考试结束前

2021年4月高等教育自学考试全国统一命题考试

数据结构

(课程代码02331)

注意事项:

1.本试卷分为两部分，第一部分为选择题，第二部分为非选择题。

2.应考者必须按试题顺序在答题卡(纸) 指定位置上作答，答在试卷上无效。

3.涂写部分、画團部分必须使用2B铅笔，书写部分必须使用黑色字迹签字笔。

第一部分选择题

一、单项选择题:本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

1.下列选项中，不属于线性结构的是

A.线性表

B.双向链表

C.循环队列

D.二叉树

2.某线性表L含有n个元素，采用单循环链表保存，仅有尾指针指向链表的终端结点。在最后一个结点之后插入一个结点及蒯除第一 个结点的时间复杂度分别是

A.0(1)和 0(1)

B.0(1)和 O(n)

C. O(n)和 0(1)

D.0(n)和 O(n)

3.下列应用中会用到栈的是.

A.计算后缀表达式的值

B.图的广度优先遍历

C.对数组进行希尔排序

D.对散列表进行查找

4.设栈初始为空，入栈序列为1.2, 3.4,5，下列选项中，不可能得到的出栈序列是

A.1,2,3,4,5

B. 3,1.4.2,5

C. 4,3.2,5, 1

D. 5,4,3.2, I

5.己知广义表LS= (C (d))。 (e, ()). (g, h), (m, n))》head(LS) 是

A. C

B. (c)

C. (c, (d))

D. (C1J)(.,(0)

6.设线性表采用顺序存储方式保存，每个元素占8个存储单元。第1个元素的存储地址为200，则第S个元素占用的最后一个存储单元的地址是

A.239

B.240

C.247

D.248

7.一棵完全二叉树T的全部k个叶结点都在同一层中，每个分支结点都有两个孩子结点。T中包含的结点数是

A.1,2,3,4,5

B. 2.3,5,4, 1

C.3,5,1,2,4

D. 4,3,5, 1,2

11.对题10-11图进行拓扑排序，下列选项中，正确的拓扑序列是

A.1,2,3, 4,5

B. 2.3, 1,4,5 .

C.3,5.1,2, 4

D. 5,3,1,2,4

12. 下列排序方法中，不是稳定排序方法的是

A.直接插入排序

B. 冒泡排序

C.归并排序

D.快速排序

13. 已知数据序列(18, 19, 20,4,51,6, 30, 1.2) 是某种排序算法第二趟排序后得到的结果，则该算法可能是

A.选择排序

B.冒泡排序

C.直接插入排序 D.快速排序

14. 对有序表(1,3.9.12,32,41.45.62.75.77)进行二分查找，查找关键字9时，进行比较的关键字依次是

A.1.3,9

B. 32,3, 9

C.32, 12,9

D.41, 12, 9

1s.分别使用下列数据序列建立二叉排序树，能得到高度最高的二叉树的是

A. 10,8,9,6, 12,11, 13

B. 10,6,8,9, 12.11,13

C. 10,12, II, 13,8,6, 9

D.10,8,6,9,12, 13, I1

第二部分非选择题

二、填空题:本大题共10小题， 每小题2分，共20分。

16.数据的运算，即对数据元素施加的操作，是定义在数据的___________结构上的。

17.在顺序表中，因为访问任一结点的方式是__________， 所以访问每个结点的时间复杂度均为0(1)。

18.带头结点的链队列可以由一个头指针和一个尾指针唯一确定。当头指针和尾指针相等时，表示队列_

_________

19.稀疏矩阵采用压缩存储，只保存非零元素，得到的顺序存储结构称为__________

20.广义表(a),(b,c), (d,e, (f,g. h))的表尾是._________

21.中序线索化二叉树的过程，是在中序遍历过程中用线索取代_________

22.在有n个顶点、e条边的无向连通图中，e的取值范围是_________.

23.对数据序列进行升序排序。采用堆排序算法时，首先应对初始数据建立_____________堆。

24.在无序数组中进行查找操作，应使用的查找方法是_________.

25. -棵高度为2的4阶B树中能够保存的关键字个数最多是__________

三、解答题:本大题共4小题，每小题5分，共20分。

26.请画出题26图所示的二叉树对应的树或森林。

以上“2021年4月自考02331数据结构真题及答案”由湖南自考网指导老师收集整理。